package dfs;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 46. 全排列
 * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
 * https://leetcode-cn.com/problems/permutations/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liweiw/
 */

public class Permutations_46 {
    public List<List<Integer>> permute(int[] nums) {
        int len = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        if (len == 0) {
            return res;
        }

        // 表示已经走过的路径
        List<Integer> path = new ArrayList<>();
        // 判断当前节点是否已经遍历过，免得再次遍历
        boolean[] used = new boolean[len];

        dfs(nums, len, 0, path, used, res);
        return res;
    }

    /**
     *
     * @param nums
     * @param len 二叉树的深度
     * @param depth 当前路径的长度
     * @param path 当前遍历的路径
     * @param used
     * @param res
     */
    private void dfs(int[] nums, int len, int depth, List<Integer> path, boolean[] used, List<List<Integer>> res) {
        if (depth == len) {
            // 在 Java 中，参数传递是 值传递，对象类型变量在传参的过程中，传递的是变量的地址的副本，这些地址被添加到 res 变量。
            // 当path回到根节点，此时path为空，所以res会是空的list
            res.add(new ArrayList<>(path));
            return;
        }

        // 在非叶子节点处，产生了不同的分支，在未选择的节点中选择一个作为下一个位置
        for (int i = 0; i < len; i++) {
            if (!used[i]) {
                path.add(nums[i]);
                used[i] = true;
                dfs(nums, len, depth+1, path, used, res);
                // 开始回溯，回溯发生在从 深层结点 回到 浅层结点 的过程，代码在形式上和递归之前是对称的
                used[i] = false;
                path.remove(path.size() - 1);
            }
        }
    }

/**********************************************************************************************************************/
/***********************分割线，上面是之前的做法，下面是新的做法**************************************************************/
/**********************************************************************************************************************/

    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    boolean[] used;
    public List<List<Integer>> permute2(int[] nums) {
        used = new boolean[nums.length];
        backtrace(nums);
        return result;
    }

    // 每次都需要重头遍历，不需要startIndex
    private void backtrace(int[] nums) {
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (used[i]) {
                continue;
            }
            used[i] = true;
            path.add(nums[i]);
            backtrace(nums);
            path.removeLast();
            used[i] = false;
        }
    }

    public static void main(String[] args) {
        Permutations_46 permutations46 = new Permutations_46();
        int[] nums = {1,2,3};
        List<List<Integer>> lists = permutations46.permute2(nums);
        System.out.println(lists);
    }
}
